#include <iostream>

using namespace std;

/*
Convert the string in the following rules:
(integers that appear >=1 times)
(integers that appear >=2 times)
...
(integers that appear >=n times)
keep characters original order
example: abbbccad->abcdbcab

time complexity: O(N)

algorithm: to use a hash table to remember the frequency of each character
*/

void ReorderString( char *str )
{
	int len = strlen(str);
	int hash[256] = {0};  // hash table
	int i=0, maxFre=0;
	
	for( i=0; i<len; i++ )
	{
		hash[str[i]]++;
		if( hash[str[i]]>maxFre)
			maxFre = hash[str[i]];
	}

	int *freIndex = new int[maxFre+1];
	int *indexArr = new int[maxFre+1];
	for( i=0; i<=maxFre; i++ )
	{
		freIndex[i] = 0;
		indexArr[i] = 0;
	}
	
	for( i=0; i<256; i++ )
	{
		if( hash[i] == 0 )
			continue;
		freIndex[hash[i]]++;
	}

	for( i=maxFre-1; i>0; i-- )
	{
		freIndex[i] = freIndex[i+1]+freIndex[i];
	}

	indexArr[1] = 0; 
	for( i=2; i<=maxFre; i++ )
	{
		indexArr[i] = indexArr[i-1]+freIndex[i-1];
	}

	memset(hash, 0, 256*sizeof(int));

	// get the start index for different frequency
	char *reorderedStr = new char[len+1];
	for ( i=0; i<len; i++ )
	{
		hash[str[i]]++;
		reorderedStr[indexArr[hash[str[i]]]++] = str[i];
	}

	reorderedStr[i] = '\0';
	cout<<"original str:"<<str<<endl;
	cout<<"reordered str:"<<reorderedStr<<endl;

	delete [] reorderedStr;
	delete [] indexArr;
	delete [] freIndex;
}

int main(void)
{
	char str[] = "abbbccad";
	ReorderString(str);

	cout<<"Press any key to terminate..."<<endl;
	return getchar();
}